/**
 * Project Name:javaBaseReview
 * Package Name:com.xuwei.base.graph
 * author:David
 * Date:2015年8月22日上午9:11:20
 * Copyright (c) 2015, xw123box@126.com All Rights Reserved.
 *
 */
package com.xuwei.base.graph;

import com.xuwei.base.link.Node;
import com.xuwei.ext.exception.InvalidNodeException;
import com.xuwei.ext.exception.OutOfBoundaryException;

/**
 * 基于双向链表实现的链接表
 * @author David
 * @since 2015年8月22日 上午9:11:20
 * @version 
 * @since JDK 1.6
 */
public class LinkListDLNode implements LinkList {
	private int size;
	private DLNode head;//头结点
	private DLNode tail;//尾结点
	
	/**构建只有头尾结点的链表*/
	public LinkListDLNode() {
		size=0;
		head=new DLNode();
		tail=new DLNode();
		head.setNext(tail);
		tail.setPre(head);
		
	}
	
	protected DLNode checkPosition(Node p)throws InvalidNodeException{
		if(p==null){
			throw new InvalidNodeException("错误：p为空。");
		}
		if(p==head){
			throw new InvalidNodeException("错误：p指向头结点，非法。");
		}
		if(p==tail){
			throw new InvalidNodeException("错误：p指向尾结点，非法。");
		}
		DLNode node=(DLNode)p;
		return node;
	}
	
	@Override
	public int getSize() {
		return size;
	}

	@Override
	public boolean isEmpty() {
		return size==0;
	}

	@Override
	public Node first() throws OutOfBoundaryException {
		if(isEmpty()){
			throw new OutOfBoundaryException("错误：链接表为空。");
		}
		return head.getNext();
	}

	@Override
	public Node last() throws OutOfBoundaryException {
		if(isEmpty()){
			throw new OutOfBoundaryException("错误：链接表为空。");
		}
		return tail.getPre();
	}

	@Override
	public Node getNext(Node p) throws InvalidNodeException,
			OutOfBoundaryException {
		DLNode node=checkPosition(p);
		node=node.getNext();
		if(node==tail){
			throw new OutOfBoundaryException("错误：已经是链接表尾端。");
		}
		return node;
	}

	@Override
	public Node getPre(Node p) throws InvalidNodeException,
			OutOfBoundaryException {
		DLNode node=checkPosition(p);
		node=node.getPre();
		if(node==head){
			throw new OutOfBoundaryException("错误：已经是链接表前端。");
		}
		return node;
	}

	@Override
	public Node insertFirst(Object e) {
		DLNode node=new DLNode(e,head,head.getNext());
		head.getNext().setPre(node);
		head.setNext(node);
		size++;
		return node;
	}

	@Override
	public Node insertLast(Object e) {
		DLNode node=new DLNode(e,tail.getPre(),tail);
		tail.getPre().setNext(node);
		tail.setPre(node);
		size++;
		return node;
	}

	@Override
	public Node insertAfter(Node p, Object e) throws InvalidNodeException {
		DLNode node=checkPosition(p);
		DLNode newNode=new DLNode(e,node,node.getNext());
		node.getNext().setPre(newNode);
		node.setNext(newNode);
		size++;
		return newNode;
	}

	@Override
	public Node insertBefore(Node p, Object e) throws InvalidNodeException {
		DLNode node=checkPosition(p);
		DLNode newNode=new DLNode(e,node.getPre(),node);
		node.setPre(newNode);
		size++;
		return newNode;
	}

	@Override
	public Object remove(Node p) throws InvalidNodeException {
		DLNode node=checkPosition(p);
		Object obj=node.getData();
		node.getPre().setNext(node.getNext());
		node.getNext().setPre(node.getPre());
		size--;
		return obj;
	}

	@Override
	public Object removeFirst() throws OutOfBoundaryException {
		return remove(head.getNext());
	}

	@Override
	public Object removeLast() throws OutOfBoundaryException {
		return remove(tail.getPre());
	}

	@Override
	public Object replace(Node p, Object e) throws InvalidNodeException {
		DLNode node=checkPosition(p);
		Object obj=node.getData();
		node.setData(e);
		return obj;
	}

	@Override
	public Iterator elements() {
		return new LinkListIterator(this);
	}

	@Override
	public void printLink() {
		DLNode p=head.getNext();
		System.out.println("head->");
		while(p!=tail){
			System.out.print((p.getData())+"->");
			p=p.getNext();
		}
		System.out.println("tail");
		
	}

	@Override
	public boolean addAll(LinkList list) {
		Iterator it = list.elements();
		for(it.first();!it.isDone();it.next()){
			Object obj = it.currentItem();
			insertLast(obj);
		}
		return true;
	}
	
}
